Google Code Jam/2010/2/a/a.cpp

   1 #include <algorithm>
   2 #include <iostream>
   3 #include <iterator>
   4 #include <sstream>
   5 #include <fstream>
   6 #include <cassert>
   7 #include <climits>
   8 #include <cstdlib>
   9 #include <cstring>
  10 #include <string>
  11 #include <cstdio>
  12 #include <vector>
  13 #include <cmath>
  14 #include <queue>
  15 #include <deque>
  16 #include <stack>
  17 #include <list>
  18 #include <map>
  19 #include <set>
  20
  21 using namespace std;
  22
  23 template <class T> string toStr(const T &x){
  24 stringstream s; s << x; return s.str();
  25 }
  26
  27 template <class T> int toInt(const T &x){
  28 stringstream s; s << x; int r; s >> r; return r;
  29 }
  30
  31 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  32 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  33 #define D(x) cout << #x " = " << (x) << endl
  34
  35 const double EPS = 1e-9;
  36 int cmp(double x, double y, double tol = EPS){
  37   return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  38 }
  39
  40 const int MAXN = 55;
  41 vector<int> d[2 * MAXN];
  42 vector<int> e[2 * MAXN];
  43
  44 #define minimize(x, y) if ((y) < (x)) (x) = (y)
  45
  46 bool startsWith(vector<int> a, vector<int> b){
  47   assert(b.size() <= a.size());
  48   for (int i = 0; i < b.size(); ++i){
  49     if (a[i] != b[i]) return false;
  50   }
  51   return true;
  52 }
  53
  54 void DV(vector<int> v){
  55   for (int i = 0; i < v.size(); ++i){
  56     cout << v[i] << " ";
  57   }
  58   cout << endl;
  59 }
  60
  61 int reflect(vector<int> a){
  62   if (a.size() == 1) return 0;
  63   int ans = a.size();
  64   D("a");
  65   DV(a);
  66
  67   int half = (a.size() + 1) / 2;
  68
  69   for (int i = half; i < a.size(); ++i){
  70     vector<int> l;
  71     for (int j = 0; j < half; ++j) l.push_back(a[i]);
  72
  73     vector<int> l_reversed = l;
  74     reverse(l.begin(), l.end());
  75
  76     vector<int> t;
  77
  78     t = l;
  79     for (int k = 0; k < l_reversed.size(); ++k) t.push_back(l_reversed[k]);
  80
  81     assert(t.size() >= a.size());
  82     if (startsWith(t, a)){
  83       minimize(ans, t.size() - a.size());
  84     }
  85
  86     t = l;
  87     for (int k = 1; k < l_reversed.size(); ++k) t.push_back(l_reversed[k]);
  88     assert(t.size() >= a.size());
  89     if (startsWith(t, a)){
  90       minimize(ans, t.size() - a.size());
  91     }
  92
  93
  94   }
  95   return ans;
  96 }
  97
  98 void solve(){
  99   int n;
 100   cin >> n;
 101   for (int i = 0; i < 2 * n; ++i){
 102     d[i].clear();
 103     e[i].clear();
 104   }
 105
 106   for (int i = 0; i < n; ++i){
 107     for (int j = 0; j <= i; ++j){
 108       int x;
 109       cin >> x;
 110       d[i].push_back(x);
 111     }
 112   }
 113   for (int i = n-2; i >= 0; --i){
 114     for (int j = 0; j <= i; ++j){
 115       int x;
 116       cin >> x;
 117       d[2*n-2-i].push_back(x);
 118     }
 119   }
 120
 121   // for (int i = 0; i < 2 * n; ++i){
 122   //   for (int j = 0; j < d[i].size(); ++j){
 123   //     cout << d[i][j] << " ";
 124   //   }
 125   //   cout << endl;
 126   // }
 127
 128   vector<int> seen(2*n, 0);
 129   for (int j = 0; j < n; ++j){
 130     int s = j + 1;
 131     for (int i = (n - 1) - j; i <= (n - 1) + j; i += 2){
 132       e[j].push_back( d[i][seen[i]++] );
 133     }
 134   }
 135
 136   for (int j = n - 2; j >= 0; --j){
 137     int s = j + 1;
 138     for (int i = (n - 1) - j; i <= (n - 1) + j; i += 2){
 139       e[2*n -2 - j].push_back( d[i][seen[i]++] );
 140     }
 141   }
 142
 143
 144   // for (int i = 0; i < 2*n; ++i){
 145   //   for (int j = 0; j < e[i].size(); ++j){
 146   //     cout << e[i][j] << " ";
 147   //   }
 148   //   cout << endl;
 149   // }
 150
 151   int max_a = -1, max_b = -1;
 152   for (int i = 0; i < 2*n; ++i){
 153     max_a = max(max_a, reflect(d[i]));
 154     max_b = max(max_b, reflect(e[i]));
 155   }
 156   D(max_a), D(max_b);
 157   int add = max_a + max_b;
 158   int ans = 0;
 159
 160   n = 2*n + 1;
 161   for (int i = 0; i < add; ++i){
 162     ans += n;
 163     n += 2;
 164   }
 165   cout << ans << endl;
 166 }
 167
 168 int main(){
 169   int T;
 170   cin >> T;
 171   for (int i = 0; i < T; ++i){
 172     printf("Case #%d: ", i);
 173     solve();
 174   }
 175   return 0;
 176 }